package leetcode_题库;

import java.util.Arrays;

public class _733_图像渲染 {
    public static void main(String[] args) {
        int[][] arr = new int[][]{{1,1,1},{1,1,0},{1,0,1}};
        int sr = 1;
        int sc = 1;
        int color = 2;
        System.err.println(Arrays.deepToString(floodFill(arr,sr,sc,color)));
    }

    public static int[][] floodFill(int[][] image, int sr, int sc, int color) {
        dfs(image,sr,sc,image[sr][sc],color);
        return image;
        /*
            > 2022/08/22 11:00:11
            解答成功:
                执行耗时:0 ms,击败了100.00% 的Java用户
                内存消耗:42.4 MB,击败了41.27% 的Java用户
         */
    }

    //深度优先算法
    public static void dfs(int[][] image,int sr,int sc,int oldColor,int color){
        //超出边界
        boolean isOverIndex = sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length;
        //当前块和新颜色一样（没必要修改），或者当前块和旧颜色不一样。
        boolean isColorForbidden = image[sr][sc] == color || image[sr][sc] != oldColor;

        if (isColorForbidden || isOverIndex){
            return;
        }
        //更新旧颜色
        oldColor = image[sr][sc];
        //赋值
        image[sr][sc] = color;
        //深度优先
        dfs(image,sr-1,sc,oldColor,color);
        dfs(image,sr,sc-1,oldColor,color);
        dfs(image,sr+1,sc,oldColor,color);
        dfs(image,sr,sc+1,oldColor,color);
    }
}
